Generally speaking, operating systems permit the organization of code such that conceptually, multiple tasks are executed simultaneously while, in reality, the operating system is switching between threads on a timed basis. A thread is considered to be a unit of work in a computer system, and a CPU switches or time multiplexes between active threads. A thread is sometimes referred to as a process; however, for purposes of this description, a thread is considered to be an active entity within a process; the process including a collection of memory, resources, and one or more threads.
A real-time operating system may provide for both space partitioning and time partitioning. In the case of space partitioning, each process is assigned specific memory and input/output regions. A process can access only memory assigned to it unless explicit access rights to other regions are granted; i.e. only if another process decides that it will share a portion of its assigned memory. In the case of time partitioning, there is a strict time and rate associated with each thread (e.g., a thread may be budgeted for 5000 ms every 25,000ms or forty times per second) in accordance with a fixed CPU schedule. A single, periodic thread could, for example, be assigned a real-time budget of 500 ms to accommodate worst-case conditions; i.e. involving all paths and all code. In many cases, however, the thread may need only a portion (e.g. 50 ms) of its 500 ms budget. The unused 450 ms is referred to as slack, and absent anything further, this unused time is wasted. To avoid this, some operating systems utilize slack pools to collect unused time that may then be utilized by other threads in accordance with some predetermined scheme; e.g. the first thread that needs the additional budget takes all or some portion of it. Alternatively, access to the slack pool is based on some priority scheme; e.g. threads that run at the same rate are given slack pool access priority. Still another approach could involve the use of a fairness algorithm. Unfortunately, none of these approaches result in the efficient and predictable use of slack.
Thus, it should be clear that time-partitioned real-time operating systems require that a specific CPU time budget be given to each thread in the system. This budget represents the maximum amount of time the thread can control the CPU's resources in a given period. A thread can run in a continuous loop until its CPU budget is exhausted, at which point an interrupt is generated by an external timer. The operating system then suspends the execution of the thread until the start of its next period, allowing other threads to execute on time. A thread execution status structure is provided to keep track of initial and remaining CPU budget. Since threads must be budgeted for worst-case conditions, only a portion of the budgeted CPU time is utilized in many cases thus reducing CPU efficiency, and slack mechanisms represent only a partial solution.
In view of the foregoing, it should be appreciated that it would be desirable to provide a method for maintaining the benefits of rigid time partitioning in a real-time operating system while increasing CPU efficiency. This is accomplished by permitting a donor thread to transfer excess or unused CPU budget to a specific beneficiary thread. Additional desirable features will become apparent to one skilled in the art from the foregoing background of the invention and the following detailed description of a preferred exemplary embodiment and appended claims.